The Atari Compendium/The Atari Compendium (Toad Computers) (1994).iso/files/prgtools/mint/filesy~1/mfsdefrg.zoo/buffers.c

C/C++ Source or Header | 1993-10-18 | 17.9 KB | 671 lines

/*
 * buffers.c - buffer management for the Linux file system degragmenter.
 * buffers.c,v 1.5 1993/01/07 14:48:47 linux Exp
 *
 * Copyright (C) 1992, 1993 Stephen Tweedie ([e-mail])
 *
 * This file may be redistributed under the terms of the GNU General
 * Public License.
 *
 */

/* Modified for Minixfs/MiNT by S N Henson 1992 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include "defrag.h"

#define sizeof_buffer (sizeof(*pool) + block_size)
#define buffer(i) ((Buffer *) \
             (((char *) pool) + (i) * sizeof_buffer))

/* The buffer pool is a unified buffer space containing both the
   pending pool and the rescue pool.  The pending pool holds buffers
   waiting to be written to disk as part of the sequential write of
   optimised zones; the rescue pool holds the contents of zones about
   to be overwritten by blocks from the write pool.

   The select set is an arbitrary subset of the whole buffer pool.
   This feature is used in various places to select a group of buffers
   for reading or writing.

   The buffer pool and hash table will not necessarily be totally in
   synch with the relocation maps d2n_map and n2d_map.  It is possible
   for a buffer to exist for a block which, according to the
   relocation maps, is still on disc.  This is because the relocation
   maps are NOT modified by the creation or deletion of pool buffers,
   but only by the actual reading or writing of those pool buffers.
   (The basis of the defragmenter's optimisation is the deferring as
   long as possible of reads and writes, and the sorting of bulk
   reads/writes to improve performance.)
*/

int pool_size = 512;
Buffer *pool;
Buffer *first_free_buffer;
Buffer **select_set;
int select_set_size;
int free_buffers, count_output_buffers, count_rescue_buffers;

int count_buffer_writes = 0, count_buffer_reads = 0;
int count_write_groups = 0, count_read_groups = 0;
int count_buffer_migrates = 0, count_buffer_forces = 0;
int count_buffer_read_aheads = 0;

/* We will hash buffered blocks on the least significant bits of the
   block's dest_zone */
#define HASH_SIZE 1024
static Buffer * (hash[HASH_SIZE]) = {0};
#define hash_list(zone) (hash[(zone) % (HASH_SIZE)])

/* First of all, the primitive buffer management functions: allocation
   and freeing of buffer blocks. */

/* Set up the buffer tables and clear the hash table.  This must be
   called after the fs-dependent code has been initialised (typically
   in read_tables() ) so that the block size variables have been
   correctly initialised. */
void init_buffer_tables()
{
    int i;
    if (debug)
        printf ("DEBUG: init_buffer_tables()\n");

    for (i=0; i<HASH_SIZE; i++)
        hash[i] = 0;
    pool = (Buffer *) malloc (pool_size * sizeof_buffer);
    if (!pool)
        die ("Unable to allocate buffer pool.");
    memset (pool, 0, pool_size * sizeof_buffer);
    select_set = (Buffer **) malloc (pool_size *
                     sizeof(*select_set));
    if (!select_set)
        die ("Unable to allocate pool select set");
    select_set_size = 0;
    /* Set up the free buffer list */
    for (i=0; i<pool_size-1; i++)
    {
        buffer(i)->next = buffer(i+1);
    }
    buffer(pool_size-1)->next = 0;
    first_free_buffer = buffer(0);
    free_buffers = pool_size;
    count_output_buffers = count_rescue_buffers = 0;
}

/* Lookup a block in the hash table.  Returns a pointer to the entry
   in the hash list (ie. doubly indirected), or zero. */
static Buffer ** hash_lookup (Block zone)
{
    Buffer ** b;
    b = &(hash_list(zone));
    while (*b)
    {
        if ((*b)->dest_zone == zone)
            return b;
        b = &((*b)->next);
    }
    return 0;
}

/* Allocate an unused buffer from the pool. */
Buffer * allocate_buffer (Block zone, BufferType btype)
{
    Buffer * b;
    if (!first_free_buffer)
        die ("No free buffers");
    assert (free_buffers);
    assert (!(hash_lookup(zone)));

    /* Remove a buffer from the free list */
    b = first_free_buffer;
    first_free_buffer = first_free_buffer->next;
    assert (!b->in_use);
    b->in_use = 1;

    /* Set up the buffer fields */
    b->dest_zone = zone;
    b->btype = btype;
    b->full = 0;

    /* Update buffer counts */
    free_buffers--;
    switch (btype)
    {
    case OUTPUT:
        count_output_buffers++;
        break;
    case RESCUE:
        count_rescue_buffers++;
        break;
    }

    /* Link the buffer into the hash table */
    b->next = hash_list(zone);
    hash_list(zone) = b;

    assert ((count_rescue_buffers + count_output_buffers +
         free_buffers) == pool_size);
    return b;
}

/* Free up a buffer from the buffer pool.  Manage the free buffer list
   and hash table appropriately. */
void free_buffer (Buffer *b)
{
    Buffer **p;
    if (debug)
        printf ("DEBUG: free_buffer (%lu)\n", b->dest_zone);
    assert (b->in_use);
    assert (first_free_buffer ? free_buffers : !free_buffers);
    /* Assert : throwing away a buffer's data is illegal unless
       the zone is on disk somewhere. */
    assert (n2d(b->dest_zone));
    b->in_use = 0;

    /* Unlink this buffer from the hash table */
    p = hash_lookup (b->dest_zone);
    assert (p);
    assert ((*p) == b);
    *p = b->next;

    /* Link the buffer into the free list */
    b->next = first_free_buffer;
    first_free_buffer = b;

    /* Update buffer counts */
    free_buffers++;
    switch (b->btype)
    {
    case OUTPUT:
        count_output_buffers--;
        break;
    case RESCUE:
        count_rescue_buffers--;
        break;
    }
}

/* Set a buffer's type - used to migrate blocks from the RESCUE to the
   OUTPUT pool. */
void set_buffer_type (Buffer *b, BufferType btype)
{
    if (debug)
        printf ("DEBUG: set_buffer_type (%lu:%d, %d)\n",
            b->dest_zone, b->btype, btype);
    if (b->btype == btype)
        return;
    switch (b->btype)
    {
    case OUTPUT:
        count_output_buffers--;
        break;
    case RESCUE:
        count_rescue_buffers--;
        break;
    }
    b->btype = btype;
    switch (btype)
    {
    case OUTPUT:
        count_output_buffers++;
        break;
    case RESCUE:
        count_rescue_buffers++;
        break;
    }
    assert ((count_rescue_buffers + count_output_buffers +
         free_buffers) == pool_size);
}


/* Select a group of buffers based on an arbitrary selection predicate */
void select_buffers (int (*fn) (const Buffer *))
{
    int i;
    if (debug)
        printf ("DEBUG: select_buffers()\n");

    select_set_size = 0;
    for (i=0; i<pool_size; i++)
    {
        if (buffer(i)->in_use && fn(buffer(i)))
            select_set[select_set_size++] = buffer(i);
    }
    if (debug)
        printf ("DEBUG: selected %d buffers\n", select_set_size);
}

/* Compare two buffers based on their dest_zone fields, for use by
   the stdlib qsort() function */
static int compare_buffer_zones(const void *a, const void *b)
{
    Block azone, bzone;
    azone = (*((Buffer **) a))->dest_zone;
    bzone = (*((Buffer **) b))->dest_zone;

    if (azone < bzone)
        return -1;
    if (azone == bzone)
        return 0;
    return 1;
}

/* Compare two buffers again, this time based on their source zone */
static int compare_buffer_zones_for_read (const void *a, const void *b)
{
    Block azone, bzone;
    azone = n2d((*((Buffer **) a))->dest_zone);
    bzone = n2d((*((Buffer **) b))->dest_zone);

    if (azone < bzone)
        return -1;
    if (azone == bzone)
        return 0;
    return 1;
}

/* Sort the current select_set based on buffer dest_zone.  Sorting
   buffers in this manner before a read or write will significantly
   improve i/o performance, but is not essential for correct running
   of the program. */
void sort_select_set (void)
{
    if (debug)
        printf ("DEBUG: sort_select_set()\n");
    qsort (select_set, select_set_size, sizeof (*select_set),
           compare_buffer_zones);
}

/* Perform a similar sort, but sort on source zones for an order
   suitable for reading the select set. */
void sort_select_set_for_read (void)
{
    if (debug)
        printf ("DEBUG: sort_select_set_for_read()\n");
    qsort (select_set, select_set_size, sizeof (*select_set),
           compare_buffer_zones_for_read);
}

/*
 * check_zone_nr checks to see that *nr is a valid zone nr. It dies if
 * it isn't.
 */
void check_zone_nr (Block nr)
{
    if (debug)
        printf ("DEBUG: check_zone_nr (&%d)\n", nr);
    if (nr < first_zone)
        printf ("Zone nr %d < first_zone.\n", nr);
    else if (nr >= zones)
        printf ("Zone nr %d > zones.\n", nr);
    else
        return;
    die ("Invalid zone number");
}

/*
 * read_current_block reads block nnr into the buffer at addr.
 */
void read_current_block (Block nnr, char * addr)
{
    if (debug)
        printf ("DEBUG: read_block (&%d, %d)\n", nnr, (int) addr);
    if (!nnr)
        return;
    check_zone_nr(nnr);

    if (block_size * (nnr) != lseek (IN, block_size * (nnr), SEEK_SET))
        die ("seek failed in read_block");
    if (block_size != read (IN, addr, block_size))
        die ("Read error: bad block in read_block.");
}

/*
 * write_current_block writes block nr to disk.
 */
void write_current_block (Block nnr, char * addr)
{
    int r;

    if (debug)
        printf ("DEBUG: write_block(%d, %d)\n", nnr, (int) addr);
    check_zone_nr(nnr);
    if (block_size * nnr != lseek (IN, block_size * nnr, SEEK_SET))
        die ("seek failed in write_block");
    if (readonly)
        return;
    if (block_size != (r = write (IN, addr, block_size)))
        printf ("Write error: bad block (%d,%d) in write_block.\n", nnr, r);
    if (blocks_until_sync++ >= SYNC_PERIOD)
    {
        sync();
        blocks_until_sync = 0;
    }
}

/* read/write_old_block function as read_block and write_block, but using
   the zone map to follow blocks which may have been swapped to make room for
   optimised zones. */
void read_old_block (Block onr, char *addr)
{
    check_zone_nr(onr);
    read_current_block (d2n(onr), addr);
}

void write_old_block (Block onr, char *addr)
{
    check_zone_nr(onr);
    write_current_block (d2n(onr), addr);
}


/* Read/write _Buffer_s.  The read/write_old/new_block routines work
   on arbitrary blocks and arbitrary memory locations; the Buffer
   read/write routines, on the other hand, interact fully with the
   zone relocation maps and Buffer data structures from the buffer
   pool. */

void read_buffer_data (Buffer *b)
{
    Block source;
    if (debug)
        printf ("DEBUG: read_buffer_data (%lu)\n",
            b->dest_zone);
    assert (b->in_use);
    if (b->full)
        return;
    source = n2d(b->dest_zone);
    /* Don't bother reading here if we are in readonly mode; there
       will be no need to write it back at any time. */
    if (!readonly)
        read_current_block (source, b->data);
    d2n(source) = 0;
    n2d(b->dest_zone) = 0;
    b->full = 1;
    count_buffer_reads++;
    return;
}

void write_buffer_data_at (Buffer *b, Block dest)
{
    if (debug)
        printf ("DEBUG: write_buffer_data_at (%lu, %lu)\n",
            b->dest_zone, dest);
    assert (b->in_use & b->full);
    write_current_block (dest, b->data);
    assert (!n2d(b->dest_zone));
    assert (!d2n(dest));
    d2n(dest) = b->dest_zone;
    n2d(b->dest_zone) = dest;
    count_buffer_writes++;
}

void write_buffer_data (Buffer *b)
{
    write_buffer_data_at (b, b->dest_zone);
}


/***********************************************************************
   The disk relocation routines: the working core of the defragmenter.
   These routines are responsible for implementing the disk block
   relocation defined by the forward and reverse relocation maps
   d2n_map and n2d_map.
 ***********************************************************************/

void read_select_set ()
{
    int i;
    sort_select_set_for_read();
    if (!select_set_size)
        return;
    if (verbose>1)
        printf ("Reading %d blocks...\n", select_set_size);
    for (i=0; i < select_set_size; i++)
    {
        assert (!select_set[i]->full);
        read_buffer_data (select_set[i]);
    }
    count_read_groups++;
}

void write_select_set ()
{
    int i;
    sort_select_set();
    if (!select_set_size)
        return;
    if (verbose>1)
        printf ("Writing %d blocks...\n", select_set_size);
    for (i=0; i < select_set_size; i++)
    {
        assert (select_set[i]->in_use &&
            select_set[i]->full);
        write_buffer_data(select_set[i]);
    }
    count_write_groups++;
}

void free_select_set()
{
    int i;
    for (i=0; i < select_set_size; i++)
        free_buffer (select_set[i]);
    select_set_size = 0;
}

/* A few useful buffer selection predicates... */
int output_buffer_p (const Buffer *b)
{
    return (b->btype == OUTPUT);
}

int empty_buffer_p (const Buffer *b)
{
    return (!b->full);
}

int rescue_buffer_p (const Buffer *b)
{
    return (b->btype == RESCUE);
}

int true (const Buffer *b)
{
    return 1;
}


/* Routines for reading and flushing data */
void read_all_buffers()
{
    /* Select and sort all (non-empty) buffers for reading */
    select_buffers (empty_buffer_p);
    read_select_set();
}

void flush_output_pool()
{
    read_all_buffers ();
    select_buffers (output_buffer_p);
    if (!select_set_size)
        return;
    if (verbose>1)
        printf ("Saving: ");
    write_select_set();
    free_select_set();
}

/* Here we employ various methods for getting rid of some of the
   buffers in the buffer pool.  There are three methods used, in
   order of preference:
   flush output buffers: Buffers waiting to be sequentially written to
        disk are written now.
   If that fails to free more than 25% of buffers:
   flush rescue buffers: Rescue buffers whose destination zones are
           empty (ie. already moved into the output pool and
        hence to disk) are flushed, by migrating them
        immediately to the output pool.
   If that fails to free more than 20% of the buffers, drastic action
   is necessary:
   force rescue buffers: Rescue buffers are sorted, and a number of
        rescue buffers destined for later disk zones are
        written to free space at the end of the disk (NOT to
        their ultimate destinations, though).  We choose later
        rescue buffers to flush in preference to earlier
        buffers, in anticipation of soon being able to migrate
        early rescued blocks to the output pool. */
void get_some_buffer_space()
{
    int i, count = 0;
    Block dest;

    flush_output_pool();
    if ((free_buffers * 4) > pool_size)
        return;

    /* OK, try migrating rescue buffers to the output pool */
    for (i=0; i<pool_size; i++)
    {
        if (buffer(i)->in_use &&
            buffer(i)->btype == RESCUE &&
            d2n(buffer(i)->dest_zone) == 0)
        {
            set_buffer_type(buffer(i), OUTPUT);
            count++;
            count_buffer_migrates++;
        }
    }
    if (verbose>1)
        printf ("Migrated %d rescued blocks%s", count,
            count ? ": " : ".\n");
    flush_output_pool();
    if ((free_buffers * 5) > pool_size)
        return;

    /* Serious trouble - more than 80% of the pool is occupied by
       unsaveable rescue buffers.  We'll have to force some of
       them to disk.  (The algorithm I'm using tries hard to avoid
       this, since it is the only occasion where a disk block may
       have to be be moved more than once during relocation.) */
    select_buffers (true);
    sort_select_set ();
    assert (select_set_size + free_buffers == pool_size);
    /* Select the top 25% of rescue buffers for forcing (this is
       an entirely arbitrary number; in fact, most of the numbers
       in this function could probably be tweaked to tune
       performance, but these seem to work OK. */
    dest = zones-1; count = 0;
    if (verbose>1)
        printf ("Pool too full - forcing buffers...");
    for (i = select_set_size-1; i >= ((select_set_size*3)/4); i--)
    {
        while (d2n(dest))
            dest--;
        write_buffer_data_at (select_set[i], dest);
        free_buffer (select_set[i]);
        count_buffer_forces++;
        count++;
    }
    if (verbose>1)
        printf (" %d buffers recovered.\n", count);
    select_set_size = 0;
}

void remap_disk_blocks (void)
{
    Block source, dest = first_zone, dest2;
    Buffer **p;

    if (debug)
        printf ("DEBUG: remap_disk_blocks()\n");
    if (verbose)
        printf ("Relocating disk blocks - this could take a while.\n");

    /* Walk through each disk block sequentially, rescuing
       previous contents and reading the new contents into the
       output buffer. */
    do
    {
        if (verbose && !(dest & 1023))
        {
            printf ("Relocating : %d MB...\n",
                (dest / 1024));
        }

        /* Don't try to save stuff to disk until we are */
        /* running out of free buffers. */
        if (free_buffers < 4)
        {
            get_some_buffer_space ();
        }
        assert (free_buffers >= 4);

        /* Use the reverse relocation map to obtain the block
           which should go in this space */
        source = n2d(dest);
        /* Zero means this block cannot be found on disk.
           Either it should remain empty (it may  be a bad
           block), or it has already been read into the rescue
           pool.  If source==dest, the block is already in
           place. */
        if (source == dest)
            continue;
        /* We may have already read the source block into the
           rescue pool; look for the block (indexed by dest)
           in the hash table */
        p = hash_lookup (dest);
        if (p)
        {
            /* Yes, we already have the block so make it
               an OUTPUT buffer (it must currently be a
               RESCUE buffer). */
            assert ((*p)->btype == RESCUE);
            set_buffer_type (*p, OUTPUT);
            count_buffer_read_aheads++;
        }
        else
        {
            /* No, the block is not in the hash table:
               if the block can be found on disk, read it;
               otherwise, the block will remain empty and
               can be skipped. */
            if (!source)
                continue;
            allocate_buffer (dest, OUTPUT);
        }

        /* Rescue the block about to be overwritten.  All
           buffers are referred to by their destination zone
           (according to the relocation map), NOT the zone
           that block is currently residing in.  So, work out
           the final destination of the block currently
           residing in the destination zone by looking up the
           forward relocation map. */
        dest2 = d2n(dest);
        /* Zero means that the dest block may be safely
           overwritten. */
        if (!dest2)
            continue;
        /* Check to see if we have already read this block */
        p = hash_lookup (dest2);
        if (p)
        {
            /* We have, so no need to read it again */
            continue;
        }
        /* Read the block into the rescue pool */
        allocate_buffer (dest2, RESCUE);
    } while (++dest < zones);
    /* We have got to the end, so flush any remaining buffers. */
    flush_output_pool ();
    assert (!count_output_buffers);
    assert (!count_rescue_buffers);
    assert (free_buffers == pool_size);
}